def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
    def max_num(nums, k):
            # single表示一个数被选择的次数
            # drop表示当前已经丢弃多少个数字了
        n = len(nums)
        single = n - k
        drop = 0
        res = []
        for num in nums:
            while res and drop < single and num > res[-1]:
                res.pop()
                drop += 1
            res.append(num)
        return res[:k]
        
    m, n = len(nums1), len(nums2)
        # 从一个数组中选i个数，另一个数组选k-i个数
    res = []
    for i in range(max(0, k-n), min(k, m)+1):
        num1 = max_num(nums1, i)
        num2 = max_num(nums2, k-i)
            # 按照顺序依次取两个数中较大的一个加入结果数组中
        p, q = 0, 0
        tmp = []
        while p < i and q < k-i:
            if num1[p:] > num2[q:]:
                tmp.append(num1[p])
                p += 1
            else:
                tmp.append(num2[q])
                q += 1
        if p < i:
            tmp += num1[p:]
        if q < k-i:
            tmp += num2[q:]
        res = max(res, tmp)
    return res
"""
class Solution:
    def __init__(self):
        self.track = ''
        self.res = []

    def traceback(self, total, left, right, track) -> str:
        if left < 0 or right < 0:
            return
        if left > right:
            return
        if left == 0 and right == 0:
            self.res.append(track)
            return

        
        self.traceback(total, left - 1, right, track + '(')

        self.traceback(total, left, right - 1, track + ')')

    def generateParenthesis(self, n: int) -> List[str]:
        self.traceback(n, n, n, self.track)
        return self.res

class Solution:

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)
        if n == 0:
            return None
        if n == 1:
            return lists[0]
        mid = n // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next
"""

#贪心
from alg import Solution
class Solution:
    def largestOddNumber(self, num: str) -> str:
        n = len(num)
        for i in range(n-1,-1,-1):
            if int(num[i])%2==1:
                return num[:i+1]
        return ""

    s = Solution
    result = s.largestOddNumber("123456")
    print(result)



#回溯
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from typing import List

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        def dfs(node, current_sum, path):
            if not node:
                return
            current_sum += node.val
            path.append(node.val)
            if not node.left and not node.right and current_sum == targetSum:
                result.append(path[:])
            dfs(node.left, current_sum, path)
            dfs(node.right, current_sum, path)
            path.pop()

        result = []
        dfs(root, 0, [])
        return result


root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(1)

solution = Solution()
result = solution.pathSum(root, 22)
print(result)



#动态规划
from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]

class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        candyVec = [1] * len(ratings)
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candyVec[i] = candyVec[i - 1] + 1
        for j in range(len(ratings) - 2, -1, -1):
            if ratings[j] > ratings[j + 1]:
                candyVec[j] = max(candyVec[j], candyVec[j + 1] + 1)
        return sum(candyVec)


class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        if not n: return []
        board = [['.'] * n for _ in range(n)]
        res = []
        def isVaild(board,row, col):
            #判断同一列是否冲突
            for i in range(len(board)):
                if board[i][col] == 'Q':
                    return False
            # 判断左上角是否冲突
            i = row -1
            j = col -1
            while i>=0 and j>=0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # 判断右上角是否冲突
            i = row - 1
            j = col + 1
            while i>=0 and j < len(board):
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True

        def backtracking(board, row, n):
            # 如果走到最后一行，说明已经找到一个解
            if row == n:
                temp_res = []
                for temp in board:
                    temp_str = "".join(temp)
                    temp_res.append(temp_str)
                res.append(temp_res)
            for col in range(n):
                if not isVaild(board, row, col):
                    continue
                board[row][col] = 'Q'
                backtracking(board, row+1, n)
                board[row][col] = '.'
        backtracking(board, 0, n)
        return res


class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        people.sort(key=lambda x: (-x[0], x[1]))
        que = []

        for p in people:
            que.insert(p[1], p)
        return que

class Solution:
    def maxArea(self, height) :#盛水最多的容器
        i,j=0,len(height)-1
        water=0
        while i!=j:
            minH=min(height[i],height[j])
            water=max(water,minH*(j-i))
            while height[i] <= minH and i<j:
                i+=1
            while height[j] <= minH and i<j:
                j-=1
        return water
    def maxSubArray(self, nums) :#最大子序列和
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(dp[i-1] + nums[i], nums[i])
        return max(dp)
    def permute(self, nums) :#全排列
        def backtrack(first=0):
            # 所有数都填完了
            if first == n:
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        n = len(nums)
        res = []
        backtrack()
        return res

